/*Implemeting List data type of python using C language*/


#include<stdio.h>
#include<malloc.h>




struct node{
		int val;
		struct node* next;
	   };

struct node *start=NULL;
struct node *end=NULL;

void display()
{
struct node *p=start;
printf("\nThe current list is ");
while(p!=NULL)
	{
	printf("%d ",p->val);
	p=p->next;
	}
}



void append(int a)
{
struct node *new;
new=(struct node*)malloc(sizeof(struct node));
new->next=NULL;
new->val=a;
if (start==NULL||end==NULL)
	{
	start=new;
	end=new;
	}
else 
	{
	end->next=new;
	end=new;
	}

}

void reverse()
{
struct node *tmp=NULL, *p=start, *pb=NULL, *q=NULL;
while (p!=NULL)
	{
	tmp=p->next;
	p->next=pb;
	pb=p;
	p=tmp;
	}
start=q;
start=end;
end=q;
}

int count(int el)
{int a=0;
struct node *p=start;
while (p!=NULL)
	{
	if (p->val==el) a++;
	p=p->next;
	}
return a;
}


int pop(int i)
{
struct node *p=start,*q=start,*r=NULL;
int m;
if (i==1)
{
	m=start->val;
	start=start->next;
	return m;
}

if (i==0)
{ 
q=NULL;
while(p->next->next!=NULL)
	{
	p=p->next;
	}
q=p->next;
end = p;
end->next=NULL;
free (q);
}
else
{
for(int j=0;j<i-1;j++,p=p->next)
{
	if (p==start) continue;
	q=q->next;
}
q->next=p->next;
m=p->val;
free(p);
return m;


}	
	
}

int search(int m)
{
int n=0;
struct node *p=start;
while(p!=NULL)
	{n++;
	if (p->val==m)
		return n;
	p=p->next;
	}
return -1; 
}

void remov(int m)
{int n;
int p=search(m);
if (p==-1)
{
 printf("\nNO SUCH ELEMENT!");
}
else
{n= pop(p);
}

}


void insert(int value, int pos)
{struct node *p=start,*q=NULL;




q=(struct node *)malloc(sizeof(struct node));
q->val=value;
if (pos==1)
{	q->next=start;
	start=q;
}
else
{
for (int i=0; i<pos-1;i++,p=p->next);
q->next=p->next;
p->next=q;
}
}

void sort()
{
int temp;
struct node *p=start,*q=start;
while(p!=NULL)
	{
	q=start;
	while(q->next!=NULL)
		{
		if((q->val) > (q->next->val))
			{
			temp=q->val;
			q->val=q->next->val;
			q->next->val=temp;
			}
		q=q->next;
		}
	p=p->next;
	}
}

void merge()
{int m,n;
printf("\nEnter the number of elements of the second list");
scanf("%d",&m);
for (int i=0;i<m;i++)
{
	printf("\nEnter the %d element : ",i+1);
	scanf("%d",&n);
	append(n);
}
}


	
int main()
{
int ch=0,m,n;
while (ch!=10)
{
	printf("\n\t\t\tMENU\n1. Append\n2. Insert\n3. Index\n4. Merge two lists\n5. Sort\n6. Count\n7. Remove\n8. Pop\n9. Reverse\n10. Exit\nEnter your choice ");
	scanf("%d",&ch);
	switch(ch)
	{
		case(1): printf("\nEnter the element: ");
			scanf("%d",&m);
			append(m);
			display(); break;
		case(2): printf("\nEnter the position you want to insert the element: ");
			scanf("%d",&n);
			printf("\nEnter the element: ");
			scanf("%d",&m);
			insert(m,n);
			display(); break;
		case(3): printf("\nEnter the element you want to search: ");
			scanf("%d",&m);
			n=search(m);
			printf("\n The element is found at position %d.",n);
			display(); break;
		case(4):merge();
			display(); break;
		case(5):sort();
			display(); break;
		case(6):printf("\nEnter the element you want to count: ");
			scanf("%d",&m);
			n=count(m);
			printf("\nNumber of occurances is %d\n",n);
			display(); break;
		case(7):printf("\nEnter the element you want to remove");
			scanf("%d",&m);
			remov(m);
			display(); break;
		case(8):printf("\nEnter the position of element you want to pop (0 for the last element)");
			scanf("%d",&m);
			n=pop(m);
			printf("\nThe removed element is %d\n",n);
			display(); break;
		case(9):reverse();
			display(); break;
		case(10):return 0;
		default:printf("\nWrong choice!");
	}
}

}



